import java.util.*;

public class Solution488 {
    char[] chars={'R','Y','B','G','W'};
    public static class State{
        int[] ints;
        String board;
        int step;

        public State(int[] ints, String board,int step) {
            this.ints= ints;
            this.board = board;
            this.step = step;
        }
    }
    public int findMinStep(String board, String hand) {
        int[] ini=new int[5];
        Arrays.fill(ini,0);
        Map<Character,Integer> map=new HashMap<>();
        map.put('R',0);
        map.put('Y',1);
        map.put('B',2);
        map.put('G',3);
        map.put('W',4);
        for (int i=0;i<hand.length();i++){
            ini[map.get(hand.charAt(i))]++;
        }
        Queue<State> queue=new ArrayDeque<>();
        queue.offer(new State(ini,board,0));
        while (!queue.isEmpty()){
            State state=queue.poll();
            if (state.board.equals("")){
                return state.step;
            }
            for (char aChar : chars) {
                int count=state.ints[map.get(aChar)];
                if (count==0){
                    continue;
                }
                //可以插入board里面没有的球
                state.ints[map.get(aChar)]--;
                for (int i=0;i<state.board.length();i++){
                    StringBuilder stringBuilder=new StringBuilder();
                    String newBoard=stringBuilder.append(state.board.substring(0,i)).append(aChar).append(state.board.substring(i)).toString();
                    queue.offer(new State(Arrays.copyOf(state.ints,5),check(newBoard),state.step+1));
                    while (i<state.board.length() && aChar==state.board.charAt(i)){   //剪枝，相同的状态不再考虑
                        i++;
                    }
                }
                //state.ints[map.get(aChar)]++;  这句恢复状态不写，竟然也是对的？？真的不懂
            }
        }
        return -1;
    }

    String check(String board){
        boolean flag=false;
        do{
            flag=false;
            if (board.length()>=3){
              for (int i=0;i<board.length()-2;i++){
                  if (board.charAt(i)==board.charAt(i+1) && board.charAt(i+1)==board.charAt(i+2)){
                      int t=i;
                      while(t+1<board.length() && board.charAt(t)==board.charAt(t+1)){
                          t++;
                      }
                      board=board.substring(0,i).concat(board.substring(t+1));
                      flag=true;
                      break;
                  }
              }
            }
        }while(flag);
        return board;
    }

    public static void main(String[] args) {
        System.out.println(new Solution488().findMinStep("RRYGGYYRRYGGYYRR","GGBBB"));
    }
}